A subgraph of an edge-coloured complete graph is called rainbow if all itsedges have different colours. In 1980 Hahn conjectured that every properlyedge-coloured complete graph $K_n$ has a rainbow Hamiltonian path. Althoughthis conjecture turned out to be false, it was widely believed that such acolouring always contains a rainbow cycle of length almost $n$. In this paper,improving on several earlier results, we confirm this by proving that everyproperly edge-coloured $K_n$ has a rainbow cycle of length $n-O(n^{3/4})$. Oneof the main ingredients of our proof, which is of independent interest, showsthat a random subgraph of a properly edge-coloured $K_n$ formed by the edges ofa random set of colours has a similar edge distribution as a truly random graphwith the same edge density. In particular it has very good expansionproperties.
展开▼
